package 剑指offer.树;

import java.util.ArrayList;
import java.util.LinkedList;

/*
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

二叉树的层序遍历
 */
public class 第32题从上到下打印二叉树 {

    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

     /*
     二叉树的层序遍历：
     先打第一层、再打第二层、再。。
     那么也就是打印每一层的左右子树
     那么每一层会有多个节点，这些节点需要通过一个队列保存
     然后拿出一个队头节点，输出他的左右子树，再拉下一个队头节点，如此反复
      */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.pop();
            ans.add(node.val);
            // 注意判空
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return ans;
    }
}
